package splitsumequalsubset

import "fmt"

// 迭代+回溯的方法遍历所有可能的分割方法，并判断是否存在元素和相等的子集
func SplitSumEqualSubset(nums []int) bool {
	used := make(map[int]bool, len(nums)) // 记录哪些元素被用过了
	var backtrack func(used map[int]bool, start int) bool
	backtrack = func(used map[int]bool, start int) bool {
		if len(used) == len(nums) {
			return false
		}
		// 判断used和unused是否相等
		if len(used) > 0 && isEuqal(used, nums) {
			return true
		}
		for i := start; i < len(nums); i++ {
			used[i] = true
			res := backtrack(used, i+1)
			if res {
				return true
			}
			delete(used, i)
		}

		return false
	}

	return backtrack(used, 0)
}

func isEuqal(used map[int]bool, nums []int) bool {
	sumUsed := 0
	sumUnsed := 0
	for i := 0; i < len(nums); i++ {
		if _, ok := used[i]; !ok {
			sumUnsed += nums[i]
		} else {
			sumUsed += nums[i]
		}
	}

	res := sumUsed == sumUnsed
	if res {
		fmt.Println("used:", used, "sumUsed:", sumUsed, "sumUnsed:", sumUnsed)
		return true
	}
	return false
}
